home *** CD-ROM | disk | FTP | other *** search
/ Games of Daze / Infomagic - Games of Daze (Summer 1995) (Disc 1 of 2).iso / x2ftp / msdos / source / snip9503 / lls.c < prev    next >
Encoding:
C/C++ Source or Header  |  1995-03-14  |  19.7 KB  |  720 lines
  1. /* =======================================================================
  2.     LLS.c           Generic Singly Linked Lists for fixed size data.
  3.                     Each List has its own specific data size.
  4.                     This version uses a dummy head node, which prevents
  5.                     special handling of the first node.
  6.  
  7.                     v1.00  94-08-21
  8.  
  9.                     Compile with NDEBUG not defined for debugging version.
  10.                     Compile with NDEBUG defined for production version.
  11.  
  12.                     Prepared for use of a last node pointer.
  13.                     Compile with USE_LASTPTR defined to use it.
  14.  
  15.                     The node pointers are restricted to valid values.
  16.                     They point only in empty lists to invalid data.
  17.  
  18.                     Possible future enhancements:
  19.                     - List(s) of free nodes for fast node memory alloc.
  20.                       Or a special memory sub-allocator.
  21.                     - FindFirst() & FindNext().
  22.                     - Data access via first and/or last node pointers.
  23.                       (duplicate the functions and change .current to
  24.                       .first or .last)
  25.                     - Node deletion via first and/or last node pointers.
  26.                       (as for access functions, then simplify ...)
  27.  
  28.  _____              This version is Public Domain.
  29.  /_|__|             A.Reitsma, Delft, The Netherlands.
  30. /  | \  --------------------------------------------------------------- */
  31.  
  32. #include <stdarg.h>         /* variable arg handling */
  33. #include <assert.h>         /* debugging */
  34. #include "defines.h"        /* debugging incl MALLOC (re-) definition   */
  35. #include "LLS.h"            /* also includes portable.h if necessary    */
  36.  
  37. #define NO_PROBLEMS LIST_NO_PROBLEMS /* local redefinition */
  38.  
  39. struct Node
  40. {
  41.     struct Node * next;
  42.     int data;               /* also place-holder for larger items.      */
  43. };                          /* actual nodes have various sizes,         */
  44.                             /* but a fixed size within a list.          */
  45. struct ListHead
  46. {
  47.     struct Node * current;  /* will actually point to preceeding node   */
  48.     struct Node * first;    /* always points to dummy head node         */
  49.  
  50. #ifdef USE_LASTPTR
  51.  
  52.     struct Node * last;     /* will actually point to preceeding node   */
  53.  
  54. #endif
  55.  
  56.     int itemsize ;          /* zero value: used as 'list not used' flag */
  57. };
  58.  
  59. #define ERR_MEMORY          -1
  60.  
  61. #define NODE_MALLOC(list)   (struct Node *) \
  62.                             MALLOC( ListControl[ list ].itemsize \
  63.                                     + sizeof( struct Node * ), char )
  64.  
  65. #define NODE_FREE(node)     FREE(node)
  66.  
  67. /* ---- Local data ---------------------------------------------------- */
  68.  
  69. static struct ListHead * ListControl = NULL;
  70. static unsigned int ListCount ;
  71.  
  72. /* ---- LL system mangement ------------------------------------------- */
  73.  
  74. static int ListInit( int List, int ItemSize )
  75. {
  76.     struct Node * Tmp ;
  77.  
  78.     /* Create dummy head node.
  79.        This is not a part of of the ListControl structure because that can
  80.        and will move, making 'first' invalid. That _could_ be handled by
  81.        adjusting it; or by getting rid of 'first' entirely and having its
  82.        function taken over by "&.head" and ".first->next" by ".head.next".
  83.     */
  84.     if( 0 != ItemSize )
  85.     {
  86.         Tmp = NODE_MALLOC( List );
  87.         if( NULL == Tmp )
  88.         {
  89.             return ERR_MEMORY ;
  90.         }
  91.         Tmp->next = NULL;
  92.         Tmp->data = 0x4709 ; /* dummy value */
  93.     }
  94.     else
  95.         Tmp = NULL ;
  96.  
  97.     /* initialize control structure
  98.     */
  99.     ListControl[ List ].current  =
  100.     ListControl[ List ].first    = Tmp ;
  101.  
  102. #ifdef USE_LASTPTR
  103.  
  104.     ListControl[ List ].last     = Tmp ;
  105.  
  106. #endif
  107.  
  108.     ListControl[ List ].itemsize = ItemSize ; /* zero: list not used    */
  109.     return NO_PROBLEMS ;
  110. }
  111.  
  112. int LLSsystemInit( int ListCountInit )
  113. {
  114.     assert( (unsigned) ( ListCountInit -1 ) <= 20 -1 );
  115.                  /* negative is logic error (cast => neg. is large int) */
  116.                  /* higher than 20 is ridiculous for an initial setup   */
  117.                  /* zero is useless                                     */
  118.  
  119.     if( NULL != ListControl )
  120.     {
  121.         return NO_PROBLEMS ; /* LL system already initialized */
  122.     }
  123.  
  124.     ListControl = MALLOC( ListCountInit, struct ListHead );
  125.     if( NULL == ListControl )
  126.     {
  127.         return ERR_MEMORY ;
  128.     }
  129.  
  130.     for( ListCount = 0 ; ListCount < (unsigned)ListCountInit ; ListCount++ )
  131.         ListInit( ListCount, 0 ); /* just mark it as usable ... */
  132.  
  133.     /* ListCount is now ListCountInit */
  134.     assert( ListCount == (unsigned)ListCountInit );
  135.  
  136.     return NO_PROBLEMS;
  137. }
  138.  
  139. int LLScreate( int ItemSize )
  140. {
  141.     int List ;
  142.  
  143.     assert( (unsigned) ( ItemSize -1 ) < 1024 -1 ) ;
  144.                              /* limit to 1kB. A size of 0 is ridiculous */
  145.  
  146.     /* trigger automatic system initialisation if neccesary
  147.     */
  148.     if( NULL == ListControl  &&  0 != LLSsystemInit( 1 ))
  149.     {
  150.         return ERR_MEMORY ;
  151.     }
  152.  
  153.     /* Look for empty slot
  154.     */
  155.     for( List = 0; List < (int)ListCount; List++ )
  156.     {
  157.         if( 0 == ListControl[ List ].itemsize )
  158.             break;
  159.     }
  160.  
  161.     /*  What if NO EMPTY slot ???
  162.     */
  163.     if( List == (int)ListCount )
  164.     {
  165.         struct ListHead * tmp ;         /* ListControl expansion needed */
  166.  
  167.         tmp = MALLOC( ListCount + 1, struct ListHead );
  168.         if( NULL == tmp )
  169.         {                               /* realloc is not used bacause  */
  170.             return ERR_MEMORY ;         /* MALLOC is not necesarily     */
  171.         }                               /* based on malloc()            */
  172.  
  173.         memcpy( tmp, ListControl, ListCount * sizeof( struct ListHead ));
  174.         ListControl = tmp ;
  175.         ListCount++ ;
  176.     }
  177.  
  178.     /* create dummy head node and set up ListControl for the list.
  179.     */
  180.     if( ERR_MEMORY == ListInit( List, ItemSize ))
  181.     {
  182.         return ERR_MEMORY ;
  183.     }
  184.  
  185.     return List ;
  186. }
  187.  
  188. void LLSdelete( int List )
  189. {
  190.     struct Node * Tmp ;
  191.     struct Node * Old ;
  192.  
  193.     assert( (unsigned) List < ListCount );
  194.  
  195.     Tmp = ListControl[ List ].first ; /* dummy head is also deleted !!! */
  196.     while( NULL != Tmp )              /* still assuming last node has   */
  197.     {                                 /* a NULL next pointer ...        */
  198.         Old = Tmp ;
  199.         Tmp = Old->next;
  200.         NODE_FREE( Old ); /* data already presumed to be deleted */
  201.     }
  202.  
  203.     ListInit( List, 0 ); /* 0: mark list as not used. */
  204.  
  205.     return ;
  206. }
  207.  
  208. /* ---- LL system maintenance ----------------------------------------- */
  209.  
  210. int LLScheck( int List )
  211. {
  212.     if( NULL == ListControl )
  213.     {
  214.         return LIST_SYSTEM_NULL ;
  215.     }
  216.  
  217.     if( (unsigned) List >= ListCount )
  218.     {
  219.         return LIST_INV_NUMBER ;
  220.     }
  221.  
  222.     if( 0 == ListControl[ List ].itemsize )
  223.     {
  224.         return LIST_NOT_CREATED ;
  225.     }
  226.  
  227.     if( NULL == ListControl[ List ].first )
  228.     {
  229.         return LIST_ERR_HEAD ;
  230.     }
  231.  
  232.     /* Validate current pointer,
  233.        and the last node pointer if it is used ...
  234.     */
  235.     if( NULL == ListControl[ List ].current )
  236.     {
  237.         return LIST_CORRUPT7 ;    /* shouldn't be NULL with a good head */
  238.     }
  239.  
  240.     if( NULL != ListControl[ List ].first->next )       /* list empty ? */
  241.     {                                                   /* not empty    */
  242.         struct Node * tmp = ListControl[ List ].first ;
  243.  
  244.         if( NULL == ListControl[ List ].current->next )
  245.         {
  246.             return LIST_CORRUPT6 ; /* a NULL next pointer is only valid */
  247.         }                          /* for an empty list.                */
  248.  
  249.         /* look for .current in list
  250.         */
  251.         while( tmp != ListControl[ List ].current )
  252.         {
  253.             tmp = tmp->next ;
  254.  
  255.             if( NULL == tmp )
  256.             {
  257.                 return LIST_CORRUPT5 ;  /* current not found in list */
  258.             }
  259.         }
  260.  
  261. #ifdef USE_LASTPTR
  262.  
  263.         /* Found .current in list.
  264.            Now look for valid last node pointer in list
  265.         */
  266.         if( NULL == ListControl[ List ].last )
  267.         {
  268.             return LIST_ERR_LAST ;
  269.         }
  270.  
  271.         while( tmp != ListControl[ List ].last )
  272.         {
  273.             tmp = tmp->next ;
  274.             if( NULL == tmp )
  275.             {
  276.                 return LIST_CORRUPT4 ;  /* last not found in list */
  277.             }
  278.         }
  279.  
  280.         /* Found .last in list but is it really the last ?
  281.            Note that last should actually point to the preceeding node ...
  282.            Note: tmp == .last
  283.         */
  284.         if( NULL == tmp->next || NULL != tmp->next->next )
  285.         {
  286.             return LIST_CORRUPT3 ; /* a NULL next pointer is only valid */
  287.         }                          /* for an empty list. But next->next */
  288.                                    /* should be NULL for last pointer   */
  289. #endif
  290.  
  291.         return NO_PROBLEMS ;
  292.     }
  293.  
  294.     /* .first->next == NULL -> list is empty
  295.     */
  296.     if( ListControl[ List ].current != ListControl[ List ].first )
  297.     {
  298.         return LIST_CORRUPT2 ;
  299.     }
  300.  
  301. #ifdef USE_LASTPTR
  302.  
  303.     if( ListControl[ List ].last != ListControl[ List ].first )
  304.     {
  305.         return LIST_CORRUPT1 ;
  306.     }
  307.  
  308. #endif
  309.  
  310.     return LIST_EMPTY ;
  311. }
  312.  
  313. /* ---- node management ----------------------------------------------- */
  314.  
  315. int LLSnodeInsert( int List, ... )      /* insert _BEFORE_ current node */
  316. {
  317.     va_list DataPtr ;
  318.     int Retval ;
  319.  
  320.     /* set DataPtr to the address of "..."
  321.        then action, cleanup and return.
  322.     */
  323.     va_start( DataPtr, List );
  324.  
  325.     Retval = LLSnodeInsertFrom( List, DataPtr );
  326.  
  327.     va_end( DataPtr );
  328.     return Retval ;
  329. }
  330.  
  331. int LLSnodeAdd( int List, ... )          /* insert _AFTER_ current node */
  332. {
  333.     va_list DataPtr ;
  334.     int Retval ;
  335.  
  336.     /* set DataPtr to the address of "..."
  337.        then action, cleanup and return.
  338.     */
  339.     va_start( DataPtr, List );
  340.  
  341.     Retval = LLSnodeAddFrom( List, DataPtr );
  342.  
  343.     va_end( DataPtr );
  344.     return Retval ;
  345. }
  346.  
  347. int LLSnodePrepend( int List, ... )             /* insert as first node */
  348. {
  349.     va_list DataPtr ;
  350.     int Retval ;
  351.  
  352.     /* set DataPtr to the address of "..."
  353.        then action, cleanup and return.
  354.     */
  355.     va_start( DataPtr, List );
  356.  
  357.     Retval = LLSnodePrependFrom( List, DataPtr );
  358.  
  359.     va_end( DataPtr );
  360.     return Retval ;
  361. }
  362.  
  363. int LLSnodeAppend( int List, ... )               /* insert as last node */
  364. {
  365.     va_list DataPtr ;
  366.     int Retval ;
  367.  
  368.     /* set DataPtr to the address of "..."
  369.        then action, cleanup and return.
  370.     */
  371.     va_start( DataPtr, List );
  372.  
  373.     Retval = LLSnodeAppendFrom( List, DataPtr );
  374.  
  375.     va_end( DataPtr );
  376.     return Retval ;
  377. }
  378.  
  379. int LLSnodeInsertFrom( int List, void * Source )
  380. {                                       /* insert _BEFORE_ current node */
  381.     struct Node * New ;
  382.  
  383.     assert( (unsigned) List < ListCount );
  384.  
  385.     /* create new node if possible
  386.     */
  387.     New = NODE_MALLOC( List );
  388.     if( NULL == New )
  389.     {
  390.         return ERR_MEMORY ;
  391.     }
  392.  
  393.     /* fill node with data and link to previous node
  394.        Note that explicitly changing .current is not necessary!
  395.     */
  396.     memcpy( & New->data, Source, ListControl[ List ].itemsize );
  397.     New->next = ListControl[ List ].current->next;
  398.     ListControl[ List ].current->next = New ;
  399.  
  400. #ifdef USE_LASTPTR
  401.     /* advance last node pointer if needed
  402.     */
  403.     if( NULL != ListControl[ List ].last->next->next )
  404.         ListControl[ List ].last = ListControl[ List ].last->next ;
  405.  
  406. #endif
  407.  
  408.     return NO_PROBLEMS;
  409. }
  410.  
  411. int LLSnodeAddFrom( int List, void * Source )
  412. {                                        /* insert _AFTER_ current node */
  413.     struct Node * New ;
  414.  
  415.     assert( (unsigned) List < ListCount );
  416.  
  417.     /* create new node if possible
  418.     */
  419.     New = NODE_MALLOC( List );
  420.     if( NULL == New )
  421.     {
  422.         return ERR_MEMORY ;
  423.     }
  424.  
  425.     /* fill node with data and link to previous node,
  426.        with special handling if the list is empty
  427.        Note that the changing of .current is the only difference with
  428.        the LLSnodeInsertFrom() function!
  429.     */
  430.     memcpy( & New->data, Source, ListControl[ List ].itemsize );
  431.  
  432.     if( NULL != ListControl[ List ].current->next )
  433.         ListControl[ List ].current = ListControl[ List ].current->next ;
  434.  
  435.     New->next = ListControl[ List ].current->next;
  436.     ListControl[ List ].current->next = New;
  437.  
  438. #ifdef USE_LASTPTR
  439.     /* advance last node pointer if needed
  440.     */
  441.     if( NULL != ListControl[ List ].last->next->next )
  442.         ListControl[ List ].last = ListControl[ List ].last->next ;
  443.  
  444. #endif
  445.  
  446.     return NO_PROBLEMS;
  447. }
  448.  
  449. int LLSnodePrependFrom( int List, void * Source )
  450. {                                               /* insert as first node */
  451.     struct Node * New ;
  452.  
  453.     assert( (unsigned) List < ListCount );
  454.  
  455.     /* create new node if possible
  456.     */
  457.     New = NODE_MALLOC( List );
  458.     if( NULL == New )
  459.     {
  460.         return ERR_MEMORY ;
  461.     }
  462.  
  463.     /* fill node with data
  464.     */
  465.     memcpy( & New->data, Source, ListControl[ List ].itemsize );
  466.     New->next = ListControl[ List ].first->next;
  467.     ListControl[ List ].first->next = New;
  468.  
  469.     if( NULL != New->next && NULL == New->next->next )
  470.     {
  471.         /* The new node is not the only node and is the node preceeding
  472.            the actual last node.
  473.            So it is the first of only two valid nodes.
  474.            Note that before insertion of 'New ' .current was .first
  475.            As was the optional last node pointer.
  476.            Note also that this section is a consequence of using a
  477.            'trailing' current node pointer!
  478.         */
  479.         ListControl[ List ].current = New ; /* == .current->next */
  480.  
  481. #ifdef USE_LASTPTR
  482.  
  483.         ListControl[ List ].last = New ; /* == .last->next */
  484.  
  485. #endif
  486.  
  487.     }
  488.  
  489.     return NO_PROBLEMS;
  490. }
  491.  
  492. int LLSnodeAppendFrom( int List, void * Source )
  493. {                                                /* insert as last node */
  494.     struct Node * New ;
  495.  
  496.     assert( (unsigned) List < ListCount );
  497.  
  498.     /* create new node if possible
  499.     */
  500.     New = NODE_MALLOC( List );
  501.     if( NULL == New )
  502.     {
  503.         return ERR_MEMORY ;
  504.     }
  505.  
  506.     /* fill node with data
  507.     */
  508.     memcpy( & New->data, Source, ListControl[ List ].itemsize );
  509.     New->next = NULL ;
  510.  
  511. #ifdef USE_LASTPTR
  512.  
  513.     if( NULL != ListControl[ List ].last->next )    /* non empty list ? */
  514.         ListControl[ List ].last = ListControl[ List ].last->next ;
  515.     ListControl[ List ].last->next = New ;
  516.  
  517. #else
  518.  
  519.     {
  520.         struct Node * Tmp = ListControl[ List ].current;
  521.  
  522.         while( NULL != Tmp->next ) /* find last node */
  523.             Tmp = Tmp->next ;
  524.  
  525.         Tmp->next = New ;
  526.     }
  527.  
  528. #endif
  529.  
  530.     return NO_PROBLEMS;
  531. }
  532.  
  533. void LLSnodeDelete( int List )
  534. {
  535.     {
  536.         struct Node * Old = ListControl[ List ].current->next ;
  537.  
  538.         assert( (unsigned) List < ListCount );
  539.  
  540.         if( NULL == ListControl[ List ].current->next )
  541.         {
  542.             return ;  /* nothing there to delete ... */
  543.         }
  544.  
  545.         ListControl[ List ].current->next = Old->next ;
  546.         NODE_FREE( Old );
  547.     }
  548.  
  549.     /* Modification to prevent current and last node pointers pointing
  550.        past the last node of a list: adjust the current and last node
  551.        pointers when the last node was deleted
  552.     */
  553.     if( NULL == ListControl[ List ].current->next )
  554.     {
  555.         struct Node * Tmp = ListControl[ List ].first;
  556.  
  557.         if( NULL != Tmp->next )                 /* list not empty ?     */
  558.             while( NULL != Tmp->next->next )    /* find the node before */
  559.                 Tmp = Tmp->next ;               /* the last node        */
  560.  
  561.         ListControl[ List ].current = Tmp ;
  562.  
  563. #ifdef USE_LASTPTR
  564.  
  565.         ListControl[ List ].last = Tmp ;
  566.  
  567. #endif
  568.  
  569.     }
  570.     return ;
  571. }
  572.  
  573. int LLSnodeFind( int List, CompFunPtr Compare, void * DataPtr )
  574. {                        /* FindFirst/FindNext format may be needed ... */
  575.     int RetVal ;
  576.  
  577.     assert( (unsigned) List < ListCount );
  578.  
  579.     if( NULL == ListControl[ List ].first->next )
  580.     {
  581.         return 2; /* a compare usually returns just -1, 0 or 1 !!! */
  582.     }
  583.  
  584.     if( NULL == Compare ) /* default to memcmp with .itemsize */
  585.     {
  586.         while( 0 != (RetVal = memcmp( DataPtr,
  587.                                 & ListControl[ List ].current->next->data,
  588.                                 ListControl[ List ].itemsize ))
  589.                && NULL != ListControl[ List ].current->next->next )
  590.         {
  591.             ListControl[ List ].current=ListControl[ List ].current->next;
  592.         }
  593.         return RetVal ;
  594.     }
  595.     else
  596.     {
  597.         while( 0 != (RetVal = (*Compare)( DataPtr,
  598.                               & ListControl[ List ].current->next->data ))
  599.                && NULL != ListControl[ List ].current->next->next )
  600.         {
  601.             ListControl[ List ].current=ListControl[ List ].current->next;
  602.         }
  603.         return RetVal ;
  604.     }
  605. }
  606.  
  607. /* ---- current node pointer management ------------------------------- */
  608.  
  609. int  LLSnodePtr2First( int List )
  610. {
  611.     assert( (unsigned) List < ListCount );
  612.  
  613.     ListControl[ List ].current = ListControl[ List ].first ;
  614.  
  615.     return NULL != ListControl[ List ].first->next ;
  616. }
  617.  
  618. int  LLSnodePtr2Last( int List )
  619. {
  620.     assert( (unsigned) List < ListCount );
  621.  
  622. #ifdef USE_LASTPTR
  623.  
  624.     ListControl[ List ].current = ListControl[ List ].last ;
  625.  
  626.     return NULL != ListControl[ List ].first->next ;
  627.  
  628. #else
  629.  
  630.     /* special handling for empty list
  631.     */
  632.     if( NULL == ListControl[ List ].first->next )
  633.     {
  634.         return 0; /* .current also same as .first */
  635.     }
  636.  
  637.     /* Let the current node pointer point to the last valid node
  638.     */
  639.     while( NULL != ListControl[ List ].current->next->next )
  640.         ListControl[ List ].current = ListControl[ List ].current->next ;
  641.  
  642.     return 1;
  643.  
  644. #endif
  645.  
  646. }
  647.  
  648. int  LLSnodePtr2Next( int List )
  649. {
  650.     assert( (unsigned) List < ListCount );
  651.  
  652.     if( NULL == ListControl[ List ].current->next       /* empty list ? */
  653.         || NULL == ListControl[ List ].current->next->next ) /* at end ?*/
  654.     {
  655.         return 0 ;             /* note: 'at end' condition added to     */
  656.     }                          /* to prevent .current pointing past end */
  657.  
  658.     ListControl[ List ].current = ListControl[ List ].current->next ;
  659.     return 1 ;
  660. }
  661.  
  662. int  LLSnodePtr2Prev( int List )
  663. {
  664.     struct Node * Prev ;
  665.  
  666.     assert( (unsigned) List < ListCount );
  667.  
  668.     Prev = ListControl[ List ].first ;
  669.     if( NULL == Prev->next                       /* empty list or */
  670.         || ListControl[ List ].current == Prev ) /* at beginning? */
  671.     {
  672.         return 0 ;
  673.     }
  674.  
  675.     /* Find previous Node
  676.     */
  677.     while( Prev->next != ListControl[ List ].current )
  678.         Prev = Prev->next ;
  679.  
  680.     ListControl[ List ].current = Prev ;
  681.  
  682.     return 1 ;
  683. }
  684.  
  685. /* ---- stored data management ---------------------------------------- */
  686.  
  687. int LLSnodeInt( int List )
  688. {
  689.     return ListControl[ List ].current->next->data;
  690. }
  691.  
  692. long LLSnodeLong( int List )
  693. {
  694.     return *((long *) &ListControl[ List ].current->next->data );
  695. }
  696.  
  697. void * LLSnodePtr( int List )
  698. {
  699.     return *((void **) &ListControl[ List ].current->next->data );
  700. }
  701.  
  702. void FAR * LLSnodeFptr( int List )
  703. {
  704.     return *((void FAR **) &ListControl[ List ].current->next->data );
  705. }
  706.  
  707. int LLSnodeDataTo( int List, void * Destination )
  708. {
  709.     if( NULL != Destination )
  710.     {
  711.         memcpy( Destination,
  712.                 & ListControl[ List ].current->next->data,
  713.                 ListControl[ List ].itemsize );
  714.     }
  715.  
  716.     return ListControl[ List ].itemsize ;       /* size needed for blob */
  717. }
  718.  
  719. /* ==== LLS.c  end ==================================================== */
  720.